package com.leetcode.hashtable;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2019/7/1
 * @description: 无重复字符的最长子串
 * B
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 */
public class LengthOfLongestSubstring_3 {

	public static void main(String[] args) {
		///输出空格
		System.out.println((char) 0);
		String str="abccbagc";
		System.out.println(lengthOfLongestSubstring(str));
		System.out.println(lengthOfLongestSubstringOptimize("bbbbb"));
		System.out.println(lengthOfLongestSubstringStandard(str));
		///abccbagc		cba
	}

	/**
	 * Mine：
	 * 这个算法中,当出现重复的时候，每一次i移动一次，是需要优化的
	 *
	 * @param s
	 * @return
	 */
	public static int lengthOfLongestSubstring(String s) {
		///1.转为字符长度
//		char[] charArray = s.toCharArray();
		int length = s.length(), i = 0, j = 0, result = 0;
		HashSet<Character> set = new HashSet<>();
		///原来i 只是一个内部的探测指针，作用是检测
		while (i < length && j < length) {
			if (!set.contains(s.charAt(j))) {
				set.add(s.charAt(j++));
				result = Math.max(result, j - i);
			} else {
				set.remove(s.charAt(i++));
			}
		}
		return result;
	}

	/**
	 * 用 HashMap 来替代 HashSet ，优化每一次移动 i 只移动一步的情况
	 * HashMap	char-next index
	 * @param s
	 * @return
	 */
	public static int lengthOfLongestSubstringOptimize(String s) {
		///1.转为字符长度
//		char[] charArray = s.toCharArray();
		int length = s.length(), i = 0, j = 0, result = 0;
		HashMap<Character,Integer> map=new HashMap<>();
		///原来i 只是一个内部的探测指针，作用是检测
		while (i < length && j < length) {
			if (!map.containsKey(s.charAt(j))) {
				map.put(s.charAt(j++),j);
				result = Math.max(result, j - i);
			} else {
				//set.remove(s.charAt(i++));
				Integer tempInt = map.get(s.charAt(i));
				map.remove(s.charAt(i));
				i=tempInt;
			}
		}
		return result;
	}

	/**
	 * 双指针
	 *
	 * @param s
	 * @return
	 */
	public static int lengthOfLongestSubstringTwoPoint(String s) {
		int len = s.length(), i = 0, j = 0, result = 0;
		char[] chars = s.toCharArray();
		///定义字符哈希
		int[] isValid = new int[95];
		return 0;
	}


	/**
	 * 卧槽还是没有搞懂？？？ isValid
	 * todo: 2 ms
	 * todo:?????
	 * @param s
	 * @return
	 */
	public static int lengthOfLongestSubstringStandard(String s) {
		char[] strs = s.toCharArray();
		int[] isValid = new int[95];
		int result = 0;
		int max = 0;
		for (int i = 0; i < strs.length; i++) {
			///存在同个
			if (isValid[strs[i] - ' '] != 0) {
				result = max > result ? max : result;
				for (int j = i - max; j < isValid[strs[i] - ' ']; j++) {
					max--;
					isValid[strs[j] - ' '] = 0;
				}
			}
			max++;
			isValid[strs[i] - ' '] = i + 1;
		}
		return max > result ? max : result;
	}



}
